\section{Iterative Physical Planning Framework}\label{sec:framework}

The synthesis-during-planning flow proposed in this paper is formulated  as an
iterative optimization problem, in which the physical planning process works at
the outer loop, identifying the critical modules and optimizing them by calling
the high-level synthesis process.

The framework is based on a simulated annealing engine, as shown in
Fig.~\ref{fig:flow}. The optimization starts with a system design
specification, which defines the architectural modules used in the system as
well as the data flows between them. Firstly, such modules are synthesized
using the built-in high-level synthesis sub-routine. From the synthesis
results, the delay/power/variability/area of the modules are extracted and then
fed to the physical planning process. The physical planner first assigns
modules to different layers of the 3D IC stack, and then performs floorplanning
on each layer. After the floorplanning, the delay and power consumption of the
whole stack is updated with the interconnect information, while the parametric
yield and the thermal profile are updated with the spatial information. A cost
function incorporating all the constraints is then evaluated. New annealing
moves will be generated for those modules on the critical ``spots'', which
could either be modules on the critical timing paths, or modules of hottest
spots in thermal profile. Those critical modules are sent to the high-level
synthesis sub-routine, in which the delay/power/variability of the module are
optimized through design space exploration. With the updated properties of the
critical modules, a new iteration of physical planning is required. The
iterative process continues until the cost is significantly low or the
iteration counts reach a preset bound.


\begin{figure}
  % Requires \usepackage{graphicx}
  \centering
  \includegraphics[width=0.4\textwidth]{fig/3dhls.pdf}
  \caption{The iterative planning and synthesis framework}\label{fig:flow}
  \vspace{-15pt}
\end{figure}

\subsection{On-Demand High-Level Synthesis as a Tuning Knob}
In the highl-level synthesis sub-routine, the delay, power, and variability of
the input module can be optimized via a set of techniques. On unit level,
different function units with the same functionality can be chosen to
facilitate the module; on circuit level, techniques such as multi-Vdd/Vth and
device sizing can be used to tune up the modules. These optimizations can be
done on the spot, however, they can be time consuming depends on the size of
the modules.

In order to improve the design efficiency, for each module used in the design,
several candidates can be generated \emph{a priori} using the high-level
synthesis process, and a look-up table can be built with multiple choices of
delay/power/variability for the given module. In such a way the call to the
high-level synthesis sub-routine could be very fast and the running time of the
whole optimization framework can be reduced.


\subsection{Incremental 3-D Floorplanning Operation}
Layer assignment and floorplanning are the key steps in the proposed framework.
The floorplanner used in the physical planning process is based on the work
in~\cite{Hung06}, which simultaneously assign blocks to each layer and perform
floorplanning operations. There are six perturbation operations used in the
algorithm:
\begin{enumerate}
 \item Node swap, which swaps two modules.
 \item Rotation, which rotates a module.
\item Move, which moves a module around.
\item Interlayer swap, which swaps two modules at different layers.
\item Interlayer move, which moves a module to a different layer.
\item Replace, which replace a module with its alternatives.
\end{enumerate}

The first five operations are from the original work in~\cite{Hung06}.
Operation (6) is added to facilitate the design space exploration during the
physical planning process. 

\subsection{Cost Function}
 The optimization is guided by several cost factors including the chip foot-print,
 the total interconnect length, the overall timing yield of the stack, and the thermal
  efficiency.
The cost function can be written as
\begin{equation}\label{eq:cost}
cost = \alpha * area + \beta * wl + \gamma * yield + \theta * temp
\end{equation}

\subsubsection{Total Interconnect Wirelength}

With the continuous technology scaling, interconnect has emerged as the
dominant source of circuit delay and power consumption. Three-dimensional (3D)
ICs have recently recognized as a promising means to mitigate the
interconnect-related problems~\cite{Davis2005,Xie2006}. During the physical
planing process interconnect wirelength should be minimized in order to
maintain the performance benefits brought by 3D integration.

\subsubsection{Chip Foot-print}
One problem of 3D floorplanning is the final packed area of each layer must match
to avoid penalties of chip area. For example, assuming two layers L1 and L2, if the final width
of packed modules of L1 is larger than the final width of packed  modules of L2 and the height of L1 is
smaller that of L2, a significant portion of chip area is wasted due to the
need for the layer dimensions to match for manufacturing. Thus, care must also be taken in both stages
of our algorithm so that  the dimension of each layer will be $compatible$.

\subsubsection{Overall Timing Yield}
$yield$ in Equation~(\ref{eq:cost}) denotes the overall timing yield of the
design. As we mentioned in Section~\ref{sec:problem}-C, the overall timing
yield depends on not only how the modules are implemented, but also where the
modules are placed. For each synthesized module, the gate-level netlist is
provided by the high-level synthesis tool. A gate-level statistical timing
analysis tool, PrimeTime VX, is then called to analyze the arriving time
distributions of each module, taking into account the spatial correlation of
the process variations. The overall timing yield is then computed from the
yield values of each module according to Equation~(\ref{eq:tyield}).

\subsubsection{Thermal Efficiency}
$temp$ in Equation~(\ref{eq:cost}) denotes the peak temperature of the 3D chip.
Peak temperature is an effective metric of the thermal efficiency. Since
block-level thermal evaluation is used during the optimization iterations, the
peak temperature is actually the average temperature of the hottest block in
the stack.

The weighing factors $\alpha, \beta, \gamma$, and $\theta$ are carefully chosen
so that the cost factors can co-exist with their respect contributions to the
total cost functions.
